package cn.fxzhang.leetcode.contest.lccup2021;


/**
 * LCP 35. 电动车游城市
 *
 * 类型：宽度搜索
 * 题解：f[i][j] 表示城市i，电量为j时的最短时间，不断前进和更新即可
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/6)：
 * 执行用时: 5 ms, 击败了100.00%
 * 内存消耗: 38.7 MB, 击败了100.00%
 * 比赛时提交了3次，都是编译错误，看不到案例，也不知道怎么改（后两次几乎没改动，其实没必要提交）
 * 比赛后第1次提交拿到测试案例，知道了是paths存在重复路径，导致connect数组越界
 * 第2次提交是next数组越界，知道是因为自己重复加入了新节点
 * 第3次总算通过。
 *
 * 总结:通过自己随机生成测试数据，可以及时发现问题，减少提交次数
 * 【困难】通过次数206提交次数1,127
 * todo 代码写得不够优雅；貌似可以用Dijkstra
 * @author 张晓帆
 * @date 2021/4/10
 */
public class LCP_35 {

    public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
        if (start == end){
            return 0;
        }
        // 城市数量
        int n = charge.length;
        // f[i][j] 城市i，电量为j时的最短时间
        int[][] f = new int[n][cnt+1];
        // connect[i]表示跟城市i有道路的城市,connectCnt[i]表示跟城市i的城市数,map[i][j]表示城市i和j的距离
        int[][] connect = new int[n][n];
        int[][] map = new int[n][n];
        int[] connectCnt = new int[n];
        for (int i=0; i<paths.length; i++){
            int x = paths[i][0];
            int y = paths[i][1];
            if (x == y){
                continue;
            }
            try{
                // 可能存在重复的路径
                if (map[x][y] == 0) {
                    map[x][y] = paths[i][2];
                    map[y][x] = paths[i][2];
                    connect[x][connectCnt[x]++] = y;
                    connect[y][connectCnt[y]++] = x;
                } else if (map[x][y] > paths[i][2]){
                    map[x][y] = paths[i][2];
                    map[y][x] = paths[i][2];
                }
            } catch (Exception e){
                System.out.println(111);
            }
        }
        // 最短时间
        int min = Integer.MAX_VALUE;
        // 下一步要去的城市
        int[] q = new int[n];
        int len = 1;
        q[0] = start;
        while (true){
            int[] next = new int[n];
            int nlen = 0;
            boolean[] flag = new boolean[n];
            for (int i=0; i<len; i++){
                // 从城市x出发, 先充满电
                int x = q[i];
                for (int j=1; j<=cnt; j++){
                    if (f[x][j] == 0 || f[x][j-1]+charge[x]<f[x][j]) {
                        f[x][j] = f[x][j-1]+charge[x];
                    }
                }
                for (int j=0; j<connectCnt[x]; j++){
                    boolean update = false;
                    int y = connect[x][j];
                    int cost = map[x][y];
                    for (int k=cost; k<=cnt; k++){
                        if (f[y][k-cost]==0|| f[x][k]+cost<f[y][k-cost]){
                            f[y][k-cost] = f[x][k]+cost;
                            update = true;
                        }
                    }
                    if (y == end){
                        min = Math.min(min, f[y][0]);
                    }
                    if (!flag[y] && update && f[y][0]<min){
                        next[nlen++] = y;
                        flag[y] = true;
                    }
                }
            }
            if (nlen == 0){
                break;
            }
            q = next;
            len = nlen;
        }
        return min;
    }
}
